The present invention concerns a fully parallel implementation of a Fast Walsh Transform ("FWT") processor, for example a circuit structure on a silicon chip, for very rapidly performing large FWTs by parallel computation of all combinations simultaneously.
A Walsh transform is a mathematical operation that converts a set of M=2.sup.N numbers to another set of M numbers by adding and/or subtracting them in predetermined sets of combinations. Each set of combinations comprises, in essence, a summation of all M original numbers, but with their signs selected according to a respective predetermined pattern. M different sets of combinations can be calculated that correspond to M predetermined sign patterns that have the desirable property of being orthogonal, viz., comparing any sign pattern with any other shows like signs in exactly half the positions and unlike signs in the other half.
The mutual orthogonality of the sign patterns makes it possible to decompose the calculation of M combinations of M values into a calculation of N.times.(M/2) sums and N.times.(M/2) differences, which is a significant reduction in the number of adds and subtracts from M.sup.2 to M.times.N. An efficient structure for carrying out these combinations is described in more detail below.
The present invention is particularly useful in code division multiple access ("CDMA") communications techniques in cellular radio telephone communication systems such as the enhanced CDMA demodulation scheme based on successive signal subtractions, in signal strength order, of multiple CDMA signals that is described in Applicant's allowed co-pending U.S. patent application Ser. No. 07/628,359, filed Dec. 17, 1990. An embodiment of the present invention that processes one hundred twenty-eight, sixteen-bit serial values is particularly useful in such a system.
The capacity limits and other aspects of CDMA communication systems are discussed in Gilhousen, et al., "On the Capacity of a Cellular CDMA System", IEEE Trans. on Vehicular Technology, Vol. 40, pp. 303 312 (May 1991). As set forth in Applicant's above-cited co-pending U.S. patent application, CDMA allows communication signals from a plurality of users to overlap in both time and frequency. In principle, each informational data stream to be transmitted is impressed upon a much-higher-bit-rate data stream generated by a pseudorandom code generator. The informational data stream and the high-bit-rate data stream are combined by multiplying the two bit streams together, which is called coding, or spreading the spectrum of, the informational data stream. Each informational data stream, or channel, is allocated a unique spreading code, which for many reasons is advantageously a block-error correction code.
A plurality of coded information signals are transmitted on radio frequency carrier waves and jointly received as composite signals by receivers. Each of the coded signals overlaps all of the other coded signals, as well as noise-related signals, in both frequency and time. By correlating a received composite signal with one of the unique codes, the corresponding information signal can be isolated and decoded using the present FWT processor.